﻿namespace Leetcode.N0321;
public class Solution
{
    public int[] MaxNumber(int[] nums1, int[] nums2, int k)
    {
        var countMax = Math.Min(nums1.Length, k);
        var countMin = Math.Max(0, k - nums2.Length);
        var max = new int[k];
        for (int i = countMin; i <= countMax; i++)
        {
            var m1 = this.GetMaxNumber(nums1, i);
            var m2 = this.GetMaxNumber(nums2, k - i);
            var result = this.Merge(m1, m2);
            max = this.Max(max, result);
        }

        return max;
    }

    private int[] Max(int[] nums1, int[] nums2)
    {
        for (int i = 0; i < nums1.Length; i++)
        {
            if (nums1[i] > nums2[i])
            {
                return nums1;
            }
            else if (nums1[i] < nums2[i])
            {
                return nums2;
            }
        }
        return nums2;
    }

    protected internal int[] GetMaxNumber(int[] nums, int count)
    {
        var result = new int[count];
        var start = 0;
        for (int i = 0; i < result.Length; i++)
        {
            int j = nums.Length - (count - i);
            int pos = -1;
            for (; j >= start; j--)
            {
                if (nums[j] >= result[i])
                {
                    result[i] = nums[j];
                    pos = j;
                }
            }
            start = pos + 1;
        }

        return result;
    }

    protected internal int[] Merge(int[] nums1, int[] nums2)
    {
        var nums = new int[nums1.Length + nums2.Length];

        var i1 = 0;
        var i2 = 0;
        for (int i = 0; i < nums.Length; i++)
        {
            nums[i] = this.GetVal(nums1, nums2, ref i1, ref i2);
        }

        return nums;
    }

    private int GetVal(int[] nums1, int[] nums2, ref int index1, ref int index2)
    {
        if (index1 >= nums1.Length)
        {
            return nums2[index2++];
        }

        if (index2 >= nums2.Length)
        {
            return nums1[index1++];
        }

        var i1 = index1;
        var i2 = index2;
        while (i1 < nums1.Length && i2 < nums2.Length)
        {
            if (nums1[i1] > nums2[i2])
            {
                return nums1[index1++];
            }
            else if (nums1[i1] < nums2[i2])
            {
                return nums2[index2++];
            }

            i1++;
            i2++;
        }

        if (nums1.Length - i1 > 0)
        {
            return nums1[index1++];
        }

        return nums2[index2++];
    }
}
